1031. 两个非重叠子数组的最大和【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 前缀和 + 滑动窗口

1. 📝 题目描述

• leetcode

给你一个整数数组 nums 和两个整数 firstLen 和 secondLen，请你找出并返回两个非重叠 子数组 中元素的最大和*，*长度分别为 firstLen 和 secondLen。

长度为 firstLen 的子数组可以出现在长为 secondLen 的子数组之前或之后，但二者必须是不重叠的。

子数组是数组的一个 连续 部分。

---

示例 1：

输入：nums = [0,6,5,2,2,5,1,9,4], firstLen = 1, secondLen = 2
输出：20
解释：子数组的一种选择中，[9] 长度为 1，[6,5] 长度为 2。

示例 2：

输入：nums = [3,8,1,3,2,1,8,9,0], firstLen = 3, secondLen = 2
输出：29
解释：子数组的一种选择中，[3,8,1] 长度为 3，[8,9] 长度为 2。

示例 3：

输入：nums = [2,1,5,6,0,9,5,0,3,8], firstLen = 4, secondLen = 3
输出：31
解释：子数组的一种选择中，[5,6,0,9] 长度为 4，[0,3,8] 长度为 3。

---

提示：

• 1 <= firstLen, secondLen <= 1000
• 2 <= firstLen + secondLen <= 1000
• firstLen + secondLen <= nums.length <= 1000
• 0 <= nums[i] <= 1000

2. 🎯 s.1 - 前缀和 + 滑动窗口

js] <<< ./solutions/1/1.c [c] <<< ./solutions/1/1.py [py

/**
 * @param {number[]} nums
 * @param {number} firstLen
 * @param {number} secondLen
 * @return {number}
 */
var maxSumTwoNoOverlap = function (nums, firstLen, secondLen) {
  const n = nums.length
  const prefix = new Array(n + 1).fill(0)
  for (let i = 0; i < n; i++) prefix[i + 1] = prefix[i] + nums[i]
  const rangeSum = (l, r) => prefix[r] - prefix[l]

  const solve = (L1, L2) => {
    let maxFirst = 0
    let res = 0
    for (let i = L1 + L2; i <= n; i++) {
      maxFirst = Math.max(maxFirst, rangeSum(i - L1 - L2, i - L2))
      res = Math.max(res, maxFirst + rangeSum(i - L2, i))
    }
    return res
  }

  return Math.max(solve(firstLen, secondLen), solve(secondLen, firstLen))
}

• 时间复杂度：$O(n)$，其中 $n$ 是数组的长度
• 空间复杂度：$O(n)$，前缀和数组

算法思路：

• 预计算前缀和数组，方便快速计算任意子数组的和
• 分两种情况：firstLen 在前、secondLen 在后，或反过来
• 对于每种情况，维护前一个子数组的最大和，遍历后一个子数组的位置，取两者之和的最大值